import java.util.Arrays;
import java.util.Comparator;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-10-04
 * Time: 22:10
 */
public class Solution {
    public static int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int len = difficulty.length;

        // 数组记录对应的工作的难度和利润
        int[][] work = new int[len][2];
        for (int i = 0; i < len; i++) {
            work[i][0] = difficulty[i]; // 第一个值 表示工作的难度
            work[i][1] = profit[i]; // 第二个值表示对应的利润
        }
        // 根据工作的难度排序
        Arrays.sort(work, Comparator.comparingInt(o -> o[0]));

        // dp[i] 表示这个难度之前的工作的最大利润, 使得二分查找找到的直接就是最大的利润
        int[] maxProfit = new int[len];
        maxProfit[0] = work[0][1];
        for (int i = 1; i < len; i++) {
            maxProfit[i] = Math.max(maxProfit[i-1], work[i][1]);
        }

        int ans = 0;
        int people = worker.length;
        for (int i = 0; i < people; i++) {
            int capacity = worker[i];
            // 二分查找, 找到最大能完成的工作的下标
            int left = 0;
            int right = len - 1;
            while (left < right) {
                int mid = ((right-left+1)>>1) + left;
                if (work[mid][0] > capacity) {
                    right = mid - 1;
                } else {
                    left = mid;
                }
            }
            if (work[right][0] <= capacity) {
                // 该工作的下标对应的值直接就是这个难度一下利润的最大值
                ans += maxProfit[right];
            }
        }
        return ans;
    }
}
